package com.practice.niuke.new_direct_basics.class11;

/**
 * KMP算法解决的问题
 * 字符串str1和str2， str1是否包含str2， 如果包含返回str2在str1中开始的位置。
 * 如何做到时间复杂度O(N)完成？
 */
public class Code01_KMP {

    /**
     * 获取字符串m在字符串s中的匹配位置（s的长度 >= m的长度）
     * (若，字符串s的长度为N，字符串m的长度为M，则，N >= M)
     *
     * @param s 字符串s
     * @param m 字符串m
     * @return int
     */
    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        // str1
        char[] str1 = s.toCharArray();
        // str2
        char[] str2 = m.toCharArray();
        // 变量x表示str1中比对到的位置（当前遍历到的位置）
        int x = 0;
        // 变量y表示str2中比对到的位置（当前遍历到的位置）
        int y = 0;
        // str2 的next数组
        int[] next = getNextArray(str2); // O (M)
        // O(N)
        // 跳出while的条件：要么x越界(没有一个位置能匹配上)，要么y越界(匹配上了)
        while (x < str1.length && y < str2.length) {
            if (str1[x] == str2[y]) {// str1的x处 和 str2的y处相同，遍历str1的索引x和遍历str2的索引y，同时向右（后）移动一位
                x++;
                y++;
            } else if (next[y] == -1) { // next[y] == -1意味着y==0，遍历str2的索引y(比对的位置)已经无法往前（回/左）跳了，x向后（右）移动一位
                x++;
            } else {// y位置的next数组值不是-1，遍历str2的y索引，向前（左）移动到next[y]位置处。（y减小的过程）
                y = next[y];
            }
        }
        // x 越界  或者  y越界了
        return (y == str2.length) ? x - y : -1;
    }

    /**
     * 获取字符数组的next数组
     * (字符数组ms的长度为M，则求next数组的时间复杂度为O(M))
     *
     * @param ms 字符数组
     * @return int[]
     */
    public static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;//人为规定
        next[1] = 0;//人为规定
        // 变量i表示当前在求next数组的i位置的值
        int i = 2;
        // cn代表，cn位置的字符，是当前和i-1位置的字符比较的字符
        int cn = 0;
        while (i < next.length) {
            if (ms[i - 1] == ms[cn]) {
                // 如果i-1位置的字符 等于 cn位置的字符，next[i] = cn+1, cn=cn+1; i去到下一个位置继续求解next[i]
                next[i++] = ++cn;
            } else if (cn > 0) {
                // 如果i-1位置的字符 不等于 cn位置的字符，并且cn>0，cn就继续往前（左）跳到next[cn]处继续和i-1位置的字符比较。
                cn = next[cn];
            } else {
                // 如果i-1位置的字符 不等于 cn位置的字符，并且cn=0或-1，cn不能再往前（左）跳了，next[i] = 0; i去到下一个位置继续求解next[i]
                next[i++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));

    }

}
